/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.ssa;

import java.util.ArrayList;
import java.util.List;

import com.android.dx.rop.code.Insn;
import com.android.dx.rop.code.LocalItem;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeBearer;
import com.android.dx.util.Hex;

/**
 * A Phi instruction (magical post-control-flow-merge) instruction in SSA form.
 * Will be converted to moves in predecessor blocks before conversion back to
 * ROP form.
 */
public final class PhiInsn extends SsaInsn {

	/**
	 * result register. The original result register of the phi insn is needed
	 * during the renaming process after the new result register has already
	 * been chosen.
	 */
	private final int ropResultReg;

	/**
	 * {@code non-null;} operands of the instruction; built up by
	 * {@link #addPhiOperand}
	 */
	private final ArrayList<Operand> operands = new ArrayList<Operand>();

	/** {@code null-ok;} source registers; constructed lazily */
	private RegisterSpecList sources;

	/**
	 * Constructs a new phi insn with no operands.
	 * 
	 * @param resultReg
	 *            the result reg for this phi insn
	 * @param block
	 *            block containing this insn.
	 */
	public PhiInsn(RegisterSpec resultReg, SsaBasicBlock block) {
		super(resultReg, block);
		ropResultReg = resultReg.getReg();
	}

	/**
	 * Makes a phi insn with a void result type.
	 * 
	 * @param resultReg
	 *            the result register for this phi insn.
	 * @param block
	 *            block containing this insn.
	 */
	public PhiInsn(final int resultReg, final SsaBasicBlock block) {
		/*
		 * The result type here is bogus: The type depends on the operand and
		 * will be derived later.
		 */
		super(RegisterSpec.make(resultReg, Type.VOID), block);
		ropResultReg = resultReg;
	}

	/** {@inheritDoc} */
	@Override
	public PhiInsn clone() {
		throw new UnsupportedOperationException("can't clone phi");
	}

	/**
	 * Updates the TypeBearers of all the sources (phi operands) to be the
	 * current TypeBearer of the register-defining instruction's result. This is
	 * used during phi-type resolution.
	 * <p>
	 * Note that local association of operands are preserved in this step.
	 * 
	 * @param ssaMeth
	 *            method that contains this insn
	 */
	public void updateSourcesToDefinitions(SsaMethod ssaMeth) {
		for (Operand o : operands) {
			RegisterSpec def = ssaMeth.getDefinitionForRegister(
					o.regSpec.getReg()).getResult();

			o.regSpec = o.regSpec.withType(def.getType());
		}

		sources = null;
	}

	/**
	 * Changes the result type. Used during phi type resolution
	 * 
	 * @param type
	 *            {@code non-null;} new TypeBearer
	 * @param local
	 *            {@code null-ok;} new local info, if available
	 */
	public void changeResultType(TypeBearer type, LocalItem local) {
		setResult(RegisterSpec.makeLocalOptional(getResult().getReg(), type,
				local));
	}

	/**
	 * Gets the original rop-form result reg. This is useful during renaming.
	 * 
	 * @return the original rop-form result reg
	 */
	public int getRopResultReg() {
		return ropResultReg;
	}

	/**
	 * Adds an operand to this phi instruction.
	 * 
	 * @param registerSpec
	 *            register spec, including type and reg of operand
	 * @param predBlock
	 *            predecessor block to be associated with this operand
	 */
	public void addPhiOperand(RegisterSpec registerSpec, SsaBasicBlock predBlock) {
		operands.add(new Operand(registerSpec, predBlock.getIndex(), predBlock
				.getRopLabel()));

		// Un-cache sources, in case someone has already called getSources().
		sources = null;
	}

	/**
	 * Removes all operand uses of a register from this phi instruction.
	 * 
	 * @param registerSpec
	 *            register spec, including type and reg of operand
	 */
	public void removePhiRegister(RegisterSpec registerSpec) {
		ArrayList<Operand> operandsToRemove = new ArrayList<Operand>();
		for (Operand o : operands) {
			if (o.regSpec.getReg() == registerSpec.getReg()) {
				operandsToRemove.add(o);
			}
		}

		operands.removeAll(operandsToRemove);

		// Un-cache sources, in case someone has already called getSources().
		sources = null;
	}

	/**
	 * Gets the index of the pred block associated with the RegisterSpec at the
	 * particular getSources() index.
	 * 
	 * @param sourcesIndex
	 *            index of source in getSources()
	 * @return block index
	 */
	public int predBlockIndexForSourcesIndex(int sourcesIndex) {
		return operands.get(sourcesIndex).blockIndex;
	}

	/**
	 * {@inheritDoc} Always returns null for {@code PhiInsn}s.
	 */
	@Override
	public Rop getOpcode() {
		return null;
	}

	/**
	 * {@inheritDoc} Always returns null for {@code PhiInsn}s.
	 */
	@Override
	public Insn getOriginalRopInsn() {
		return null;
	}

	/**
	 * {@inheritDoc} Always returns false for {@code PhiInsn}s.
	 */
	@Override
	public boolean canThrow() {
		return false;
	}

	/**
	 * Gets sources. Constructed lazily from phi operand data structures and
	 * then cached.
	 * 
	 * @return {@code non-null;} sources list
	 */
	@Override
	public RegisterSpecList getSources() {
		if (sources != null) {
			return sources;
		}

		if (operands.size() == 0) {
			// How'd this happen? A phi insn with no operand?
			return RegisterSpecList.EMPTY;
		}

		int szSources = operands.size();
		sources = new RegisterSpecList(szSources);

		for (int i = 0; i < szSources; i++) {
			Operand o = operands.get(i);

			sources.set(i, o.regSpec);
		}

		sources.setImmutable();
		return sources;
	}

	/** {@inheritDoc} */
	@Override
	public boolean isRegASource(int reg) {
		/*
		 * Avoid creating a sources list in case it has not already been
		 * created.
		 */

		for (Operand o : operands) {
			if (o.regSpec.getReg() == reg) {
				return true;
			}
		}

		return false;
	}

	/**
	 * @return true if all operands use the same register
	 */
	public boolean areAllOperandsEqual() {
		if (operands.size() == 0) {
			// This should never happen.
			return true;
		}

		int firstReg = operands.get(0).regSpec.getReg();
		for (Operand o : operands) {
			if (firstReg != o.regSpec.getReg()) {
				return false;
			}
		}

		return true;
	}

	/** {@inheritDoc} */
	@Override
	public final void mapSourceRegisters(RegisterMapper mapper) {
		for (Operand o : operands) {
			RegisterSpec old = o.regSpec;
			o.regSpec = mapper.map(old);
			if (old != o.regSpec) {
				getBlock().getParent().onSourceChanged(this, old, o.regSpec);
			}
		}
		sources = null;
	}

	/**
	 * Always throws an exeption, since a phi insn may not be converted back to
	 * rop form.
	 * 
	 * @return always throws exception
	 */
	@Override
	public Insn toRopInsn() {
		throw new IllegalArgumentException(
				"Cannot convert phi insns to rop form");
	}

	/**
	 * Returns the list of predecessor blocks associated with all operands that
	 * have {@code reg} as an operand register.
	 * 
	 * @param reg
	 *            register to look up
	 * @param ssaMeth
	 *            method we're operating on
	 * @return list of predecessor blocks, empty if none
	 */
	public List<SsaBasicBlock> predBlocksForReg(int reg, SsaMethod ssaMeth) {
		ArrayList<SsaBasicBlock> ret = new ArrayList<SsaBasicBlock>();

		for (Operand o : operands) {
			if (o.regSpec.getReg() == reg) {
				ret.add(ssaMeth.getBlocks().get(o.blockIndex));
			}
		}

		return ret;
	}

	/** {@inheritDoc} */
	@Override
	public boolean isPhiOrMove() {
		return true;
	}

	/** {@inheritDoc} */
	@Override
	public boolean hasSideEffect() {
		return Optimizer.getPreserveLocals() && getLocalAssignment() != null;
	}

	/** {@inheritDoc} */
	@Override
	public void accept(SsaInsn.Visitor v) {
		v.visitPhiInsn(this);
	}

	/** {@inheritDoc} */
	public String toHuman() {
		return toHumanWithInline(null);
	}

	/**
	 * Returns human-readable string for listing dumps. This method allows
	 * sub-classes to specify extra text.
	 * 
	 * @param extra
	 *            {@code null-ok;} the argument to print after the opcode
	 * @return human-readable string for listing dumps
	 */
	protected final String toHumanWithInline(String extra) {
		StringBuffer sb = new StringBuffer(80);

		sb.append(SourcePosition.NO_INFO);
		sb.append(": phi");

		if (extra != null) {
			sb.append("(");
			sb.append(extra);
			sb.append(")");
		}

		RegisterSpec result = getResult();

		if (result == null) {
			sb.append(" .");
		} else {
			sb.append(" ");
			sb.append(result.toHuman());
		}

		sb.append(" <-");

		int sz = getSources().size();
		if (sz == 0) {
			sb.append(" .");
		} else {
			for (int i = 0; i < sz; i++) {
				sb.append(" ");
				sb.append(sources.get(i).toHuman() + "[b="
						+ Hex.u2(operands.get(i).ropLabel) + "]");
			}
		}

		return sb.toString();
	}

	/**
	 * A single phi operand, consiting of source register and block index for
	 * move.
	 */
	private static class Operand {

		public RegisterSpec regSpec;
		public final int blockIndex;
		public final int ropLabel; // only used for debugging

		public Operand(RegisterSpec regSpec, int blockIndex, int ropLabel) {
			this.regSpec = regSpec;
			this.blockIndex = blockIndex;
			this.ropLabel = ropLabel;
		}
	}

	/**
	 * Visitor interface for instances of this (outer) class.
	 */
	public static interface Visitor {

		public void visitPhiInsn(PhiInsn insn);
	}
}
